package me.shan.hanoi;

import java.util.Stack;
import lombok.Data;

/**
 * 非递归版汉诺塔
 *
 * @author liuchuang
 * @version 1.0
 * @since 2023/5/23 10:10
 */
public class HanoiNr {

    public static void hanoi(int n, char from, char via, char to) {
        Stack<Frame> stack = new Stack<>();
        call(n, from, via, to, stack);
        while (!stack.isEmpty()) {
            Frame frame = stack.peek();
            switch (frame.getPc()) {
                /*
                  0 如果只有一个盘子，则直接移动，输出移动过程，移动完成之后弹出栈
                  1 将n-1个盘子（序号1到n-1） 从 from 经过 to 移动到 via
                  2 将1个盘子（序号为n） 从 from 经过 via 移动到 to
                  3 将n-1个盘子（序号1到n-1） 从 via 经过 from 移动到 to
                  4 弹出栈
                 */
                case 0:
                    if (frame.getN() == 1) {
                        System.out.printf("%c -> %c\n", frame.getFrom(), frame.getTo());
                        pcGoto(4, frame);
                    }
                    break;
                case 1:
                    call(frame.getN() - 1, frame.getFrom(), frame.getTo(), frame.getVia(), stack);
                    break;
                case 2:
                    call(1, frame.getFrom(), frame.getVia(), frame.getTo(), stack);
                    break;
                case 3:
                    call(frame.getN() - 1, frame.getVia(), frame.getFrom(), frame.getTo(), stack);
                    break;
                case 4:
                    ret(stack);
                    break;
                default:

            }
            frame.setPc(frame.getPc() + 1);
        }
    }

    public static void call(int n, char from, char via, char to, Stack<Frame> stack) {
        Frame frame = new Frame(n, from, via, to);
        stack.push(frame);
    }

    public static void ret(Stack<Frame> stack) {
        stack.pop();
    }

    public static void pcGoto(Integer loc, Frame frame) {
        frame.setPc(loc - 1);
    }

    public static void main(String[] args) {
        hanoi(3, 'A', 'B', 'C');
    }

}

@Data
class Frame {

    /**
     * 程序计数器pc
     */
    private int pc;

    /**
     * 盘子的数量
     */
    private int n;

    /**
     * 从哪根柱子开始移动
     */
    private char from;

    /**
     * 经过哪根柱子
     */
    private char via;

    /**
     * 移动到哪根柱子
     */
    private char to;

    public Frame(int n, char from, char via, char to) {
        this.n = n;
        this.pc = 0;
        this.from = from;
        this.via = via;
        this.to = to;
    }
}